package q749_containVirus;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public int containVirus(int[][] isInfected) {
        // 首先用一个boolean二维数组来标记已经被病毒感染的位置
        boolean[][] settle = new boolean[51][51];
        for (int i = 0; i < isInfected.length; ++i) {
            for (int j = 0; j < isInfected[0].length; ++j) {
                if (isInfected[i][j] == 1) settle[i][j] = true;
            }
        }

        int ans = 0;
        while (true) {
            // 使用findBlocks函数可以记录每个被病毒感染并且联通的一块区域 其中每个List<int[]>是一个连续被感染的区域
            List<List<int[]>> blocks = findBlocks(isInfected);
            if (blocks.size() == 0) break;
            // max代表最大能够感染的栅格数量 wall则是需要的墙数 idx是对应最大感染的那个区域的idx
            int idx = -1, max = -1, wall = -1;
            for (int i = 0; i < blocks.size(); ++i) {
                // count函数返回一个数组 数组中第一个数字代表需要的墙壁数量 第二个则代表下一次感染的栅格数量
                int[] data = count(blocks.get(i), isInfected, settle);
                if (data[1] > max) {
                    max = data[1];
                    wall = data[0];
                    idx = i;
                }
            }

            if (wall == 0) break;
            ans += wall;
            // 此时取出能够感染最多栅格的区域 将这个区域内所有栅格归零 代表已经被墙壁围住 不再能够感染其他位置
            // 同时这个区域的settle仍然是true 所以其他栅格下一步感染也无法影响该区域
            List<int[]> cur = blocks.get(idx);
            for (int[] cell : cur) isInfected[cell[0]][cell[1]] = 0;

            // 除了idx的那块区域之外 所有的区域都要进行下一步感染
            for (int i = 0; i < blocks.size(); i++) {
                if (i == idx) continue;
                List<int[]> list = blocks.get(i);
                for (int j = 0; j < list.size(); j++) {
                    int[] a = list.get(j);
                    for (int[] dir : dirs) {
                        int x = a[0] + dir[0], y = a[1] + dir[1];
                        if (x >= 0 && x < isInfected.length && y >= 0 && y < isInfected[0].length && !settle[x][y]) {
                            isInfected[x][y] = 1;
                            settle[x][y] = true;
                        }
                    }
                }
            }

        }

        return ans;
    }

    private int[] count(List<int[]> list, int[][] grid, boolean[][] settled) {
        boolean[][] vis = new boolean[51][51];
        int[] ans = new int[2];

        for (int i = 0; i < list.size(); ++i) {
            int[] cell = list.get(i);
            for (int[] dir : dirs) {
                int x = cell[0] + dir[0], y = cell[1] + dir[1];
                if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == 0 && !settled[x][y]) {
                    ++ans[0];
                    if (!vis[x][y]) {
                        vis[x][y] = true;
                        ++ans[1];
                    }
                }
            }
        }


        return ans;
    }


    private List<List<int[]>> findBlocks(int[][] isInfected) {
        boolean[][] vis = new boolean[51][51];
        List<List<int[]>> res = new ArrayList<>();

        for (int i = 0; i < isInfected.length; ++i) {
            for (int j = 0; j < isInfected[0].length; ++j) {
                if (isInfected[i][j] == 1 && !vis[i][j]) {
                    Deque<int[]> queue = new LinkedList<>();
                    List<int[]> path = new ArrayList<>();
                    path.add(new int[]{i, j});
                    queue.offer(new int[]{i, j});
                    vis[i][j] = true;
                    while (!queue.isEmpty()) {
                        int size = queue.size();
                        for (int k = 0; k < size; ++k) {
                            int[] cur = queue.poll();
                            for (int[] dir : dirs) {
                                int x = cur[0] + dir[0], y = cur[1] + dir[1];
                                if (x >= 0 && x < isInfected.length && y >= 0 && y < isInfected[0].length && isInfected[x][y] == 1 && !vis[x][y]) {
                                    queue.offer(new int[]{x, y});
                                    path.add(new int[]{x, y});
                                    vis[x][y] = true;
                                }
                            }
                        }
                    }

                    res.add(new ArrayList<>(path));
                }


            }
        }


        return res;
    }
}
